群论 置顶 | 发布于 2021-03-05 | 分类于 群论 | 12分钟 | 2160字数 一.群 1.群的定义 对于一个集合 SSS 和定义在这个集合上的二元运算 ∗*∗ , 满足: 阅读全文 »
网络流总结 做题记录 置顶 | 发布于 2020-12-25 | 分类于 最大密度子图 、 最小割 、 最大流 、 最大点权闭合子图 、 网络流 、 费用流 | 10分钟 | 2237字数 网络流 24 题 Blog 1.二分图 阅读全文 »
平面图 置顶 | 发布于 2020-09-05 | 分类于 图论 、 平面图 | 3分钟 | 532字数 一.定义 若能将无向图 G=(V,E)G=(V,E)G=(V,E) 画在平面上使得任意两条无重合顶点的边不相交,则称 GGG 是平面图。 在平面图中,由边构成的最小区域称为面,包围该面的边数记为该面的度,特殊的,平面图外的区域也为一个面。 阅读全文 »
网络流24题 置顶 | 发布于 2020-09-05 | 分类于 最小割 、 最大流 、 最大点权闭合子图 、 网络流 、 费用流 | 35分钟 | 6084字数 其实只有 212121 道题。两道不是网络流,另一道是假题。 理论上按难度排序。 一.最大流/最小割问题 阅读全文 »
快速傅里叶变换 置顶 | 发布于 2020-09-04 | 分类于 多项式 、 fft | 27分钟 | 4640字数 一.复数 1.概念 复数就是形如 a+bia+bia+bi 的数,其中 a,ba,ba,b 是实数,且b≠0,i2=−1b≠0,i^2=- 1b=0,i2=−1。 阅读全文 »
二分图 置顶 | 发布于 2020-07-11 | 分类于 二分图 、 图论 | 9分钟 | 1902字数 一.二分图的基本知识 1.二分图的概念 ~~~~~~~ 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集,则称图G为一个二分图。我们一般把其中一部分称为x部,另一部分称为y部。 阅读全文 »
Trie树 置顶 | 发布于 2020-07-11 | 分类于 字典树 、 数据结构 、 字符串 | 11分钟 | 2216字数 一.引入 如果有一道题是这样的: 给你n个字符串组成的一个词典,m次询问,每次给出一个字符串,问它是否出现在词典中。 阅读全文 »
强连通分量 置顶 | 发布于 2020-07-11 | 分类于 图论 、 强连通分量 | 13分钟 | 2367字数 一.强连通分量的定义 在有向图G中,如果两个顶点vi,vj间(vi!=vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径(即两点互相可达),则称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量。 一个有向图是强连通的,当且仅当G中有一个回路,它至少包含每个节点一次。 阅读全文 »
回文自动机(PAM) 置顶 | 发布于 2020-07-11 | 分类于 回文自动机 、 字符串 | 6分钟 | 1212字数 一.概念 1.回文自动机 回文自动机,又叫回文树,是一种能在Θ(n)\Theta(n)Θ(n)时间玄学解决回文串问题的一种结构,代码难度也十分和蔼可亲。 阅读全文 »